Generation and adaptation of computational grids
The purpose of calculations using the finite element method is to simulate a selected physical phenomenon in a given area. In addition, a projection task such as that shown in the introductory modules in this manual has applications in computer graphics.
Many examples can be given, such as
- calculation of the temperature distribution on the selected heat-treated part,
- calculation of stresses in a specific part of the building structure,
- calculation of the deformation of the designed mobile phone when it hits the ground,
- calculation of car model deformations during a road accident,
- calculation of the blood flow field in the designed bypass in the central circulatory system,
- calculation of acoustic wave propagation on a human head model, including the inner ear model,
- calculating the propagation of electromagnetic waves on a human head model while talking on a mobile phone,
and many other applications, engineering and scientific ones.
Each of these simulations requires generating a computational mesh covering a specific area with finite elements.
Classic computational mesh generators most often generate meshes made of triangular elements in two dimensions, and meshes made of tetrahedral elements in three dimensions. There are also used meshes made of rectangular elements in two dimensions and cubic elements in three dimensions, and additionally prismatic elements and pyramids. Theoretically, it is also possible to create finite elements built of any polygons in two dimensions or polyhedra in three dimensions (see the polyDPG project).
Computational meshes built of any elements should have specific properties.
- We need to be able to define functions, often called shape functions, spanning over finite elements. Shape functions can be spanned in many ways, they can be associated with vertices, edges, faces and interiors of elements (for example, Lagrange's hierarchical polynomials). Shape functions are most often polynomials. In the case of using the Galerkin method (the classic version of the finite element method), appropriate shape functions from adjacent elements related to edges or faces are merged into global basis functions used to approximate the solution. If we want the linear combination of our basis functions to have higher continuity (so that the derivative can be calculated at each point), then these functions are spread over many adjacent elements (for example, B-spline basis functions). Therefore, it is difficult to define higher continuity basis functions on triangular or tetrahedral meshes.
- We must be able to exactly integrate our shape functions spanning the elements. This means that we must be able to define numerical integration quadratures having a finite number of points, strictly defined, so that it is possible to integrate polynomials with the zero error on a given element. Therefore, processing meshes made of polygons or polyhedra is problematic (but possible). Numerical integration does not have to be exact (e.g. it is difficult to compute numerical integrals with zero error on "crooked" manifolds) but the error of the integration must be of sufficiently low order to ensure convergence of the solution.
- Finite elements must have the right proportions. It is not good if the finite element is too elongated. A measure of the "elongation" of an element is the calculation of the area or volume of the element using the integral \( \int_E 1 d{\bf x} \). If the area or volume of an element is small (of the order \( 10^{-6} \) or less), If the area or volume of an element is small (of the order 10−6 or less), then such an element will generate numerical problems. In particular, if we generate the matrix used in the calculations of the finite element method on our mesh, then this matrix will have small numbers, and during factorization the solver, e.g. Gaussian elimination, will fail, which will be manifested by the presence of values close to zero on the diagonal of the matrix and the inability to divide the row). In the case of irregular meshes, the ratio of the diameter of the circumscribed circle to the diameter of the inscribed circle is tested. Various mathematical theories describing the convergence of the finite element method assume certain proportions of these diameters in order to guarantee the convergence of the method.
- Finite elements that make up a computational mesh cannot have duplicate vertices, edges and faces. During the finite element calculations, we calculate integrals over the entire calculation area. These integrals are broken down into individual finite elements and summed. If some elements are duplicated, we can sum up the incorrectly calculated integral. In addition, the uncertainties in the equation system are often related to the coefficients of the basis functions associated with the vertices, edges, or faces of the elements. In addition, the basis functions used in the finite element method are glued together from pieces called shape functions spanned over the individual elements. If the objects in our data structure representing vertices, edges, or faces that are duplicated, this can lead to duplicate unknowns in the equation system, and cut our underlying functions into pieces related to individual elements. This will lead to incorrect calculation results by the finite element method.
- During the finite element calculations, a regular "patch" of elements, for example forming a regular rectangle or a cube, is often created, and this "patch" is mapped by transformation to the real geometry of our modeled area using a specific projection. Then the geometry of our object is "encoded" in the form of a Jacobian change of variables from the area modeled to our "patch". Of course, this requires certain regularities in the mesh covering the physical area. In particular, it is not always possible to obtain this for meshes composed of triangular and tetrahedral elements. For triangular and tetrahedral elements, integration takes place over a single element (no need to construct patches and transformations to the reference space are made for single elements, which can always be performed.
- The sum of all finite elements must cover the entire area (not only the lack of overlapping or duplication of elements, but also the lack of holes between elements - this is important, for example, for curvilinear areas, manifolds)
- When using CAD (Computer Aided Design) systems, the geometry of the modeled object is determined by CAD objects described using B-spline, NURBS or T-spline functions (or similar), for which transformations are known to map these objects to regular patches of elements. They are automatically created by CAD systems when designing such objects. This enables easy decomposition of the created object into regular patches of elements and then performing calculations using the isogeometric finite element method. So, in this case we have a set of basis function parameters (B-spline or NURBS) that describe the geometry of the mapped object, and a second set of parameters of the same basis functions that describe the approximated physical quantities.
One of the frequently used methods of generating a computational mesh made of triangular elements is Delauney triangulation (see Fig. 1 ). Based on Delauney's ideas, the whole school of generation and adaptation of computational grids is still developing [1], [2].
The computational mesh built using Delauney's triangulation is built of triangular elements in two dimensions. We can span a circle on each triangular element (because it is possible to span a circle at any three points). The exemplary construction is presented in Fig. 2. Two-dimensional Delauney triangulation has the following property, the circles described in Delauney triangulation triangles do not contain the vertex points of other triangles.
It is also possible to construct a Delauney triangulation in three dimensions. Then the computational mesh is built of tetrahedral elements. At the vertices of the tetrahedral element, we can unfasten the sphere (we need four points to unbend the sphere). Delauney's triangulation in three dimensions, in turn, has the following property, spheres described on Delauney tetrahedra will not contain vertex points of other tetrahedra.